lectures.alex.balgavy.eu

Lecture notes from university.
git clone git://git.alex.balgavy.eu/lectures.alex.balgavy.eu.git
Log | Files | Refs | Submodules

Fixed point combinators.md (390B)

      1 +++
      2 title = "Fixed point combinators"
      3 +++
      4 
      5 # Fixed point combinators
      6 **Fixed point**
      7 M is a fixed point of F if `F M =β M`
      8 for example, every term M is a fixed point of I.
      9 
     10 **Fixed point combinator**
     11 Y is a fixed point combinator if
     12 `F M =β M (F M)` for every λ-term F
     13 
     14 examples:
     15 - Curry’s — Y = λf.(λx.f (x x)) (λx.f (x x))
     16 - Turing’s — (λx.λy.(x x y)) (λx.λy.y (x x y))